package com.tianyuan.test1;
/**二叉树*/
/**
 * 二叉树的前序遍历
 *
 * @date 2025/10/16 16:25
 * 给你二叉树的根节点root，返回它节点值的前序遍历。
 * 数据范围：二叉树的节点数量满足1≤n≤100，二叉树节点的值满足1≤val≤100，树的各节点的值各不相同
 * 输入：{1,#,2,3}
 * 返回值：[1,2,3]
 */
import java.util.*;

public class Solution {
    /**
     * 二叉树前序遍历的主方法
     * @param root 二叉树的根节点（若树为空，root为null）
     * @return 前序遍历结果的int数组（顺序：根节点 → 左子树 → 右子树）
     */
    public int[] preorderTraversal (TreeNode root) {
        // 1. 初始化ArrayList：动态存储遍历结果
        ArrayList<Integer> resultList = new ArrayList<>();// 用ArrayList是因为遍历前不知道节点总数，动态列表可灵活添加元素
        // 2. 调用递归函数，开始前序遍历
        process(resultList, root);// 传入resultList用于收集结果，root为当前要遍历的树的根节点
        // 3. 将ArrayList转换为int数组（题目要求返回int[]类型）
        return listToArray(resultList);
    }
    /**
     * 前序遍历的递归核心函数
     * 功能：遍历以root为根的二叉树，将节点值按“根→左→右”顺序存入resultList
     * @param resultList 用于收集遍历结果的动态列表
     * @param root 当前要遍历的子树的根节点
     */
    public void process(ArrayList<Integer> resultList, TreeNode root) {
        // 递归终止条件：若当前节点为null（子树为空），直接返回，不做任何操作
        if (root == null) {
            return;
        }
        // 第一步：访问当前根节点，将节点值加入结果列表（前序的核心：先处理根）
        resultList.add(root.val);
        // 第二步：递归遍历当前节点的左子树（根处理完后，优先遍历左子树）
        process(resultList, root.left);
        // 第三步：递归遍历当前节点的右子树（左子树遍历完后，再遍历右子树）
        process(resultList, root.right);
    }
    /**
     * 工具函数：将ArrayList<Integer>转换为int[]数组
     * @param resultList 存储遍历结果的动态列表
     * @return 与列表元素顺序一致的int数组
     */
    public int[] listToArray(ArrayList<Integer> resultList) {
        // 1. 创建长度与列表相同的int数组（此时已知道节点总数，可固定数组长度）
        int[] resultArray = new int[resultList.size()];
        // 2. 遍历列表，将每个元素依次存入数组
        for (int i = 0; i < resultArray.length; i++) {
            resultArray[i] = resultList.get(i);
        }
        // 3. 返回转换后的数组
        return resultArray;
    }










    public static void main(String[] args) {
        // 输入字符串：{1,#,2,3}
        String input = "1,#,2,3";

        // 根据输入构建二叉树
        TreeNode root = buildTree(input);

        // 执行前序遍历
        Solution solution = new Solution();
        int[] result = solution.preorderTraversal(root);

        // 输出结果：[1,2,3]
        System.out.println(Arrays.toString(result));
    }

    /**
     * 根据输入字符串构建二叉树
     * 输入格式示例："1,#,2,3" 表示
     *       1
     *        \
     *         2
     *        /
     *       3
     */
    private static TreeNode buildTree(String input) {
        if (input == null || input.isEmpty()) {
            return null;
        }

        // 分割字符串得到节点值列表
        String[] nodes = input.split(",");
        if (nodes[0].equals("#")) {
            return null;
        }

        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1;

        // 层序遍历构建二叉树
        while (!queue.isEmpty() && index < nodes.length) {
            TreeNode current = queue.poll();

            // 处理左子节点
            if (index < nodes.length && !nodes[index].equals("#")) {
                current.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(current.left);
            }
            index++;

            // 处理右子节点
            if (index < nodes.length && !nodes[index].equals("#")) {
                current.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(current.right);
            }
            index++;
        }

        return root;
    }

}
